//151. 反转字符串中的单词
//思路：先逆置整个字符串，再将逆置后的每个单词往前挪，让每个单词之间空一个空格，再逆置每一个单词


#include <string>
#include <algorithm>
using namespace std;

class Solution
{
public:
    string reverseWords(string& s)
    {
        reverse(s.begin(), s.end());

        int index = 0, n = s.size();
        for(int start = 0; start < n; start++)
        {
            if(s[start] != ' ')
            {
                if(index != 0) s[index++] = ' ';
                
                //前移整个单词
                int end = start;
                while(end < n && s[end] != ' ')
                {
                    s[index++] = s[end++];
                }
                // 逆置整个单词
                reverse(s.begin()+index-(end-start), s.end()+index);
                // 更新start的位置
                start = end;
            }
        }  
        s.erase(s.begin()+index, s.end());
        return s;
    }
};
